package cn.fansunion.leecode.array;

import java.util.Arrays;

/**
 * 283. 移动零<br/>
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。<br/>

请注意 ，必须在不复制数组的情况下原地对数组进行操作。<br/>
https://leetcode-cn.com/problems/move-zeroes/
 * @author wen.lei@brgroup.com
 *
 * 2022-2-19
 */
public class MoveZeroes {
    /*  示例 1:
    
        输入: nums = [0,1,0,3,12]
        输出: [1,3,12,0,0]
        示例 2:
    
        输入: nums = [0]
        输出: [0]
         
    
        提示:
    
        1 <= nums.length <= 104
        -231 <= nums[i] <= 231 - 1
         
    
        进阶：你能尽量减少完成的操作次数吗？*/
    
    /**
     * 一次for循环，“双指针”，搞不定啊。进阶：尽量减少完成的操作次数吗 TODO
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int[] numsZero = new int[nums.length];
        //全为0，直接返回
        if(Arrays.equals(numsZero, nums)) {
            return;
        }
        int curZeroIndex=-1;
        int curNotZeroIndex=-1;
        boolean swap=true;
        for(int index=0;index<nums.length;index++) {
            if(nums[index]==0) {
                if(swap) {
                    curZeroIndex=index;
                }
            }else {
                curNotZeroIndex=index;
            }
            if(curNotZeroIndex>curZeroIndex) {
                swap(nums,curNotZeroIndex,curZeroIndex);
                swap=false;
                curZeroIndex=curNotZeroIndex;
            }
        }
    }
    
   
    /**
     * 额外分配了1个数组
     * @param nums
     */
    public void moveZeroesCopy(int[] nums) {
        int[] numsZero = new int[nums.length];
        //全为0，直接返回
        if(Arrays.equals(numsZero, nums)) {
            return;
        }
        int[] newNumsZero = new int[nums.length];
        int numsNotZeroSize=0;
        for(int index=0;index<nums.length;index++) {
            if(nums[index]!=0) {
                newNumsZero[numsNotZeroSize]=nums[index];
                numsNotZeroSize++;
            }
        }
        //
        for(int index=0;index<newNumsZero.length;index++) {
            nums[index]=newNumsZero[index];
        }
    }
  
    
    /**
     * 参考“冒泡排序”
     * @param nums
     */
    public void moveZeroesBubble(int[] nums) {
        for(int i=0;i<nums.length;i++) {
            for(int j=0;j<nums.length-1;j++) {
                if(nums[j]==0) {
                    swap(nums,j,j+1);
                }
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    
    //查找次数多，交换次数少
    public void justThink(int[] nums) {
        //findFirstZeroIndex，找第1个0的位置
        //findFirstNotZeroIndexAferZeroIndex(zeroIndex)，找第1个非0的位置（在第1个0之后的）
        //如果都存在，交换元素
        for(int index=0;index<nums.length;index++) {
            
        }
    }
}
